package class23.test;

import static class23.Code02_SplitSumClosedSizeHalf.*;

public class Code02_SplitSumClosedSizeHalf {
    public static int right(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int sum = 0;
        for (int i : arr) {
            sum+=i;
        }
        if(arr.length%2 == 0){
           return   process(arr,0,sum/2,(arr.length)/2);
        }else {
          return  Math.max( process(arr,0,sum/2,arr.length/2), process(arr,0,sum/2,arr.length/2+1));
        }
    }

    private static int process(int[] arr, int index, int rest,int picks) {
        if(arr.length == index){
            return picks == 0? 0 : -1;
        }
        int exist = process(arr, index + 1, rest,picks);
        int res = -1;
        if(rest >= arr[index]){
            res = process(arr, index + 1, rest - arr[index],picks-1);
            if(res != -1){
                res = arr[index] + res;
            }
        }
        return Math.max(res,exist);
    }

    public static int dp(int[] arr){
        if(arr == null && arr.length < 2){
            return -1;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

        }
        int index = arr.length;
        int rest = sum/2;
        int pick = (index + 1)/2;
        int[][][] dp = new int[index + 1][rest + 1][pick + 1];
        for (int i = 0; i <= index; i++) {
            for (int i1 = 0; i1 < rest; i1++) {
                for (int i2 = 0; i2 <= pick; i2++) {
                    dp[i][i1][i2] =-1;
                }
            }
        }
        for (int i = 0; i < sum / 2; i++) {
            dp[index][i][0] = 0;
        }

        for (int i = index-1; i >= 0; i--) {
            for (int i1 = 0; i1 <= rest; i1++) {
                for (int i2 = 0; i2 <= pick ; i2++) {
                    int exist =  dp[i+1][i1][i2];
                    int res = -1;
                    if(i1 >= arr[i]&& i2 -1 >= 0){
                        res =dp[i+1][i1-arr[i]][i2-1];
                        if(res != -1){
                            res = arr[i] + res;
                        }
                    }
                    dp[i][i1][i2] = Math.max(res,exist);
                }
            }
        }
        if(arr.length%2==0){
            return dp[0][rest][pick];
        }else {
            return Math.max(dp[0][rest][pick],dp[0][rest][pick-1]);
        }
    }

    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 50;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * maxLen);
            int[] arr = randomArray(len, maxValue);
            int ans1 = right(arr);
            int ans2 = dp(arr);
            int ans3 = dp2(arr);
            if (ans1 != ans2 || ans1 != ans3) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
